package shuanfa;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,6,7,2,7,2,8,0};
        int[] array = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            array[i]=(int)(Math.random()*8000000);
        }
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(new Date());
        System.out.println("排序前时间：" + format);
        heapSort(array);
        //System.out.println(Arrays.toString(arr));
        String format1 = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间：" + format1);
    }
    //大顶堆调整
    //堆中leftChild = 2*parent +1; right = 2*parent +2;
    //每次调用自下往上选出父节点
    public static void heapAdjust(int[] arr,int parent,int length){
        int temp = arr[parent];//保存当前临时父节点
        int leftChild = parent *2 +1;
        while (leftChild<length){
            //如果存在右孩子节点，且右孩子节点值大于左孩子节点值，就选出右孩子节点值
            if (leftChild + 1<length && arr[leftChild+1]>arr[leftChild]){
                leftChild++;
            }
            if (temp>=arr[leftChild]){//如果父节点值大于子节点直接退出
                break;
            }
            //否则孩子节点值赋值给父节点
            arr[parent] = arr[leftChild];
            parent = leftChild;//此时之前父节点位置位于孩子节点
            leftChild = leftChild*2+1;//继续往后比较 直至循环退出
        }
        arr[parent] = temp;//最终将初始父节点值赋值给找到的位置
    }

    public static void heapSort(int[] list) {
        //循环以构建初始大顶堆
        for (int i = (list.length-1)/2; i >=0; i--) {
            heapAdjust(list,i,list.length);
        }
        //初始大顶堆根节点为最大数 即list[0]
        //循环list.length-1次找出 完成排序
        for (int length = list.length-1; length >0 ; length--) {
            //交换第一个和最后以一个元素
            int temp = list[0];
            list[0] = list[length];
            list[length] = temp;

            //重新调整大顶堆
            heapAdjust(list,0,length);
        }
    }
}
